package leetcode

import (
	"fmt"
	"math"
	"slices"
	"strings"
)

/*
1512
给你一个整数数组nums。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
*/
func numIdenticalPairs(nums []int) int {
	sum := 0
	m := make(map[int]int)
	for _, v := range nums {
		if n, f := m[v]; f {
			sum += n
			m[v] = n + 1
		} else {
			m[v] = 1
		}
	}
	return sum
}

func NumIdenticalPairs(nums []int) int {
	return numIdenticalPairs(nums)
}

// 219
func containsNearbyDuplicate(nums []int, k int) bool {
	hash := make(map[int]int)
	for idx1, v := range nums {
		if idx2, f := hash[v]; f && idx1-idx2 <= k {
			return true
		}
		hash[v] = idx1
	}
	return false
}

// 121
func maxProfit(prices []int) int {
	maxV := 0
	minPrice := 10000
	for _, price := range prices {
		if price > minPrice {
			maxV = max(maxV, price-minPrice)
		} else {
			minPrice = price
		}
	}
	return maxV
}

// 50
func myPow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	if n < 0 {
		return 1 / myPow(x, -n)
	}
	temp := myPow(x, n/2)
	if n%2 == 0 {
		return temp * temp
	} else {
		return temp * temp * x
	}
}

// 387
func firstUniqChar(s string) int {
	hash := make(map[rune]int)
	for _, v := range s {
		hash[v]++
	}
	for idx, v := range s {
		if hash[v] == 1 {
			return idx
		}
	}
	return -1
}

// 70
func climbStairs(n int) int {
	var dp []int
	dp = append(dp, 1)
	dp = append(dp, 2)
	for i := 2; i < n; i++ {
		dp = append(dp, dp[i-1]+dp[i-2])
	}
	return dp[n-1]
}

// 300
func lengthOfLIS(nums []int) int {
	var dp []int
	max1 := 0
	dp = append(dp, 1)
	for i := 1; i < len(nums); i++ {
		max2 := 0
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				max2 = max(max2, dp[j])
			}
		}
		dp = append(dp, max2+1)
	}
	for i := 0; i < len(dp); i++ {
		max1 = max(dp[i], max1)
	}
	return max1
}

// 118
func Generate(numRows int) [][]int {
	var ans [][]int
	for i := 0; i < numRows; i++ {
		var ansList []int
		for j := 0; j <= i; j++ {
			if j == 0 || j == i {
				ansList = append(ansList, 1)
			} else {
				ansList = append(ansList, ans[i-1][j-1]+ans[i-1][j])
			}
		}
		ans = append(ans, ansList)
	}
	return ans
}

func fib(n int) int {
	var dp []int
	dp = append(dp, 0)
	dp = append(dp, 1)
	for i := 2; i < n; i++ {
		dp = append(dp, dp[i-1]+dp[i-2])
	}
	return dp[n]
}

// 35
func searchInsert(nums []int, target int) int {
	var l, r int = 0, len(nums)
	if target < nums[0] {
		return 0
	} else if target > nums[r-1] {
		return r
	}
	for l < r {
		mid := (l + r) / 2
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return l
}

// 136
// 异或运算两次等于原数
func singleNumber(nums []int) int {
	num := 0
	for i := 0; i < len(nums); i++ {
		num = num ^ nums[i]
	}
	return num
}

// 26
func removeDuplicates(nums []int) int {
	idx, l, r := 0, 0, 0
	for l < len(nums) {
		r = l
		nums[idx] = nums[l]
		for r < len(nums) && nums[l] == nums[r] {
			r++
		}
		idx++
		l = r
	}
	return idx + 1
}

// 58
func lengthOfLastWord(s string) int {
	s = strings.TrimSpace(s)
	strList := strings.Split(s, " ")
	return len(strList[len(strList)-1])
}

// 283
func moveZeroes(nums []int) int {
	l, r := 0, 0
	for r < len(nums) {
		if nums[r] != 0 {
			nums[l], nums[r] = nums[r], nums[l]
			l++
		}
		r++
	}
	return l
}

// 1137
func tribonacci(n int) int {
	var dp []int
	dp = append(dp, 0)
	dp = append(dp, 1)
	dp = append(dp, 1)
	for i := 3; i <= n; i++ {
		dp = append(dp, dp[i-3]+dp[i-2]+dp[i-1])
	}
	return dp[n]
}

// 746
func minCostClimbingStairs(cost []int) int {
	var dp []int
	dp = append(dp, 0)
	dp = append(dp, 0)
	for i := 2; i < len(cost)+1; i++ {
		minCost := min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
		dp = append(dp, minCost)
	}
	return dp[len(cost)]
}

// 198
func rob(nums []int) int {
	var dp []int
	n := len(nums)

	for i := 0; i < n; i++ {
		if i == 0 {
			dp = append(dp, nums[i])
		} else if i == 1 {
			dp = append(dp, max(nums[i], nums[i-1]))
		} else {
			dp = append(dp, max(dp[i-2]+nums[i], dp[i-1]))
		}
	}
	return dp[n-1]
}

func removeElement(nums []int, val int) int {
	l, r := 0, 0

	for ; r < len(nums); r++ {
		if nums[r] != val {
			nums[l], nums[r] = nums[r], nums[l]
			l++
		}
	}

	return l
}

// 168
func ConvertToTitle(columnNumber int) string {
	var ans []rune
	for columnNumber > 0 {
		fmt.Printf("columnNumber: %v\n", columnNumber)
		remainder := columnNumber % 26
		if remainder == 0 {
			remainder = 26
		}
		ans = append(ans, rune('A'+remainder-1))
		columnNumber = (columnNumber - remainder) / 26
	}
	slices.Reverse(ans)
	return string(ans)
}

/*
 */
// 684
func findRedundantConnection(edges [][]int) []int {
	var parents []int
	func() {
		for i := 0; i <= len(edges); i++ {
			parents = append(parents, i)
		}
	}()

	var find func(x int) int
	find = func(x int) int {
		if x != parents[x] {
			parents[x] = find(parents[x])
		}
		return parents[x]
	}

	union := func(x, y int) bool {
		rootx, rooty := find(x), find(y)
		if rootx == rooty {
			return false
		}
		parents[rootx] = rooty
		return true
	}

	for _, edge := range edges {
		if !union(edge[0], edge[1]) {
			return edge
		}
	}
	return nil
}

// 62
func uniquePaths(m int, n int) int {
	var dp1 [][]int
	for i := 0; i < m; i++ {
		var dp2 []int
		for j := 0; j < n; j++ {
			if i == 0 {
				dp2 = append(dp2, 1)
			} else if j == 0 {
				dp2 = append(dp2, 1)
			} else {
				dp2 = append(dp2, dp1[i-1][j]+dp2[j-1])
			}
		}
		dp1 = append(dp1, dp2)
	}
	return dp1[m-1][n-1]
}

// 338
func countBits(n int) []int {
	var ans []int
	preNum := 0
	ans = append(ans, 0)
	for i := 1; i <= n; i++ {
		if i&i-1 == 0 {
			ans = append(ans, 1)
			preNum = i
		} else {
			ans = append(ans, 1+ans[i-preNum])
		}
	}
	return ans
}

// 88 合并有序数组
func merge(nums1 []int, m int, nums2 []int, n int) {
	// l nums1指针，r nums2指针
	l, r := 0, 0
	for l < m+n || r < n {
		if n == 0 || r >= n {
			break
		} else if m == 0 || l >= m+r {
			nums1[l] = nums2[r]
			r++
		} else if nums1[l] > nums2[r] {
			for i := m + r; i > l; i-- {
				nums1[i] = nums1[i-1]
			}
			nums1[l] = nums2[r]
			r++
		}
		l++
	}
}

// 258
func addDigits(num int) int {
	if num < 10 {
		return num
	}
	newNum := 0
	for num > 0 {
		newNum += num % 10
		num = num / 10
	}
	return addDigits(newNum)
}

// 695
func maxAreaOfIsland(grid [][]int) int {
	ans := 0
	di := []int{0, 0, 1, -1}
	dj := []int{1, -1, 0, 0}
	var dfs func(x, y int) int
	dfs = func(x, y int) int {
		if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) || grid[x][y] != 1 {
			return 0
		}
		ans := 1
		grid[x][y] = 0
		for i := 0; i < len(di); i++ {
			ans += dfs(x+di[i], y+dj[i])
		}
		return ans
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			ans = max(dfs(i, j), ans)
		}
	}
	return ans
}

// 13
func romanToInt(s string) int {
	ans := 0
	symbolValues := make(map[byte]int, 0)
	symbolValues['I'] = 1
	symbolValues['V'] = 5
	symbolValues['X'] = 10
	symbolValues['L'] = 50
	symbolValues['C'] = 100
	symbolValues['D'] = 500
	symbolValues['M'] = 1000

	for i := 0; i < len(s); i++ {
		if i < len(s)-1 && symbolValues[s[i]] < symbolValues[s[i+1]] {
			ans -= symbolValues[s[i]]
		} else {
			ans += symbolValues[s[i]]
		}
	}
	return ans

}

// 14
func longestCommonPrefix(strs []string) string {
	prefix := strs[0]
	for i := 1; i < len(strs); i++ {
		prefix = commonPrefix(prefix, strs[i])
	}
	return prefix
}

func commonPrefix(str1 string, str2 string) string {
	length := min(len(str1), len(str2))
	idx := 0
	for idx < length && str1[idx] == str2[idx] {
		idx++
	}
	return str1[:idx]
}

// 28
func strStr(haystack string, needle string) int {
	idx := 0
	i := 0
	for ; i < len(haystack); i++ {
		if idx == len(needle) {
			break
		}
		if haystack[i] == needle[idx] {
			idx++
		} else {
			i = i - idx
			idx = 0
		}
	}
	if idx == len(needle) {
		return i - idx
	} else {
		return -1
	}
}

// 5
// i到j 是回文字符串
func longestPalindrome(s string) string {
	var dp [1000][1000]bool
	idx, maxLen := 0, 0
	for L := 1; L <= len(s); L++ {
		for i := 0; i < len(s); i++ {
			j := L - 1 + i
			if j >= len(s) {
				break
			}
			if L <= 2 && s[i] == s[j] {
				dp[i][j] = true
				maxLen = max(L, maxLen)
				idx = i
			} else if L <= 2 && s[i] != s[j] {
				dp[i][j] = false
			} else {
				if s[i] != s[j] {
					dp[i][j] = false
				} else if s[i] == s[j] && dp[i+1][j-1] {
					dp[i][j] = true
					maxLen = max(L, maxLen)
					idx = i
				} else if s[i] == s[j] {
					dp[i][j] = false
				}
			}
		}
	}
	return s[idx : maxLen+idx]
}

// 200
var di = []int{1, -1, 0, 0}
var dj = []int{0, 0, 1, -1}

func numIslands(grid [][]byte) int {
	sum := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				sum += dfs(grid, i, j)
			}
		}
	}
	return sum

}

func dfs(grid [][]byte, x, y int) int {
	if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) || grid[x][y] == '0' {
		return 0
	}
	grid[x][y] = '0'
	//dfs修改同一座岛 状态
	for i := 0; i < len(di); i++ {
		dfs(grid, x+di[i], y+dj[i])
	}
	fmt.Println("---")
	return 1
}

// 6
func convert(s string, numRows int) string {
	n, t := numRows, numRows*2-2
	if n == 1 || len(s) < n {
		return s
	}

	var ans []byte
	for i := 0; i < n; i++ {
		for j := 0; j+i < len(s); j = j + t {
			ans = append(ans, s[j+i])
			if i > 0 && i < n-1 && j+t-i < len(s) {
				ans = append(ans, s[j+t-i])
			}
		}
	}

	return string(ans)
}

// 7
func reverse(x int) int {
	sum := 0
	for x != 0 {
		if sum > math.MaxInt/10 || sum <= math.MinInt {
			return 0
		}
		sum = sum*10 + x%10
		x /= 10
	}

	return sum
}
